| 遗传算法解决旅行商问题（TSP） | 您所在的位置：网站首页 › 遗传算法 tsp问题 › 遗传算法解决旅行商问题（TSP） |
|
遗传算法与生物进化学说
1885年年，达尔文用自然选择来解释物种的起源和生物的进化，达尔文的自然选择学说包括三个方面： 遗传变异生存斗争和适者生存上世纪20年代，一些学者用统计生物学和种群遗传学重新解释达尔文自然选择理论，形成现代综合进化论，种群遗传学认为： 在一定地域中一个物种的全体成员构成一个种群生物的进化是种群的进化，每一代个体基因型的改变会影响种群基因库的组成，而种群基因库组成的变化就是这一种群的进化遗传算法中与生物学相关的概念和术语与优化问题中的描述的关系： 个体：解种群：解集/解空间适应度：评价/目标/寻优函数选择、交叉、变异：产生新解的方法 遗传算法的计算机实现上世纪60年代中期，Holland提出位串编码技术。这种技术适用于变异和交叉操作，而且强调将交叉作为主要的遗传操作。Holland将该算法用于自然和人工系统的自适应行为研究中，在1975出版了开创性著作“Adaptation in Natural and Artifical System”。之后，他将算法应用到优化以及学习中，并将其命名为遗传算法（简称GA）。 遗传算法基本思路： 计算开始时，随机初始化一定数目的个体，并计算每个个体的适应度值，产生第一代（初始种群）。如果不满足优化准则，开始新一代的计算：按照适应度值选择个体，产生下一代；父代按一定概率进行交叉操作，产生子代；所有的子代按一定概率变异，形成新的一代；计算新子代的适应度值。这一过程循环执行，直到满足优化准则为止。流程图： 遗传算法解决TSP问题 背景 旅行商旅行商问题，即 TSP 问题（Traveling Salesman Problem）是数学领域中著名问题之一。 假设有一个旅行商人要拜访 n 个城市，他必须选择所要走的路径，路经的限制是每个城市只 能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有 路径之中的最小值。TSP 问题是一个组合优化问题。该问题可以被证明具有 NPC 计算复杂 性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。 遗传算法遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代 表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染 色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和 产生后代。后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过 程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体， 即得到问题最优的解。 思路 编码最常用策略：路径编码直接采用城市在路径中的位置来构造用于优化的状态。例：九城市TSP问题，路径：5-4-1-7-9-8-6-2-3路径编码：(5 4 1 7 9 8 6 2 3) 交叉 变异 遗传算法解决TSP问题编程实现 MATLAB实现修改Read(‘***.tsp’)读取你想要的数据集，如上图读取的是100个城市的数据集。 dsj100.tsp NAME : dsj100 COMMENT : Clustered random problem (Johnson) TYPE : TSP DIMENSION : 100 EDGE_WEIGHT_TYPE : CEIL_2D NODE_COORD_SECTION 1 981036 508139 2 534120 -42453 3 577878 -43732 4 532890 -96645 5 205322 215891 6 225923 197950 7 69842 667632 8 391965 1054524 9 310065 -10714 10 247401 754523 11 217951 218350 12 443097 54051 13 47342 630935 14 317515 713679 15 301816 1021772 16 950864 332234 17 276433 725657 18 921801 410349 19 555508 67090 20 409959 379409 21 968097 540588 22 40089 721860 23 702011 527050 24 726191 326684 25 990428 196959 26 381890 1003805 27 409527 1056227 28 675609 496310 29 971071 188552 30 932494 818793 31 936083 384774 32 835076 517826 33 120444 663239 34 648516 395774 35 402323 126508 36 307839 57178 37 397333 987582 38 314281 949219 39 105042 667806 40 1006036 468020 41 473356 311656 42 970499 257334 43 919732 458332 44 1033956 436231 45 934265 314744 46 239142 55856 47 720304 525053 48 480764 1058084 49 970063 396578 50 543132 334794 51 755587 491352 52 975653 745618 53 272842 58331 54 537123 165900 55 519742 129315 56 35924 947451 57 1064442 490895 58 489393 117496 59 631320 277543 60 261674 961159 61 534617 58056 62 691689 512673 63 182654 715277 64 945838 459916 65 627821 -838 66 1022110 283893 67 458725 143747 68 273755 -10984 69 293760 805861 70 466598 160110 71 906179 264649 72 712619 535794 73 240847 212619 74 993782 930601 75 322034 925655 76 954600 443790 77 995817 521789 78 267943 -26353 79 674673 332544 80 978160 748015 81 353466 1077036 82 371788 950118 83 779223 446051 84 525136 311620 85 1026402 609181 86 619524 -3330 87 644232 440581 88 198821 272321 89 280990 298348 90 475893 278934 91 291897 964145 92 476091 102274 93 34538 935151 94 985493 331624 95 25533 991767 96 1029016 248202 97 1041034 983317 98 922880 836157 99 754748 378532 100 193676 209011 EOF输入TSP(pop,cp,mp,mg)上图注释说明了各参数的代表意义，注意概率 |
| CopyRight 2018-2019 实验室设备网 版权所有 |